#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

class Solution{
    public:
    //My ans--超时
    vector<int> ans1(vector<int>& num){
        vector<int> answer;
        int length = num.size();
        int temp;
        for(int i = 0; i != length; i++){
            temp = 1;
            for(int j = 0; j != length; j++){
                if(i != j){
                    temp = temp * num[j];
                }
            }
            answer.push_back(temp);
        }
        return answer;
    }

    vector<int> ans2(vector<int>& num){
        int length = num.size();
        vector<int> answer(length);
        answer[0] = 1;
        for(int i = 1; i != length; i++){
            answer[i] = answer[i-1] * num[i-1];
        }
        int R = 1;
        for(int i = length-1; i >= 0; i--){
            answer[i] = answer[i] * R;
            R = R * num[i];
        }
        return answer;
    }
    
    vector<int> ans3(vector<int>& num){
        int length = num.size();
        vector<int> L(length, 0), R(length, 0);
        vector<int> answer(length);
        L[0] = 1;
        R[length-1] = 1;
        for(int i = 1; i != length; i++){
            L[i] = num[i-1] * L[i-1];
            R[length-1-i] = num[length-i] * R[length-i];
        }
        for(int i = 0; i != length; i++){
            answer[i] = L[i] * R[i];
        }
        return answer;
    }

    void show(vector<int>& num){
        int length = num.size();
        cout << "[" << ends;
        for(int i = 0; i != length-1; i++){
            cout << num[i] << ", " << ends;
        }
        cout << num[length-1] << "]" << endl;
    }
};

void test1(){
    vector<int> num = {1, 2, 3, 4};
    vector<int> ret;

    Solution s;
    // ret = s.ans1(num);
    // ret = s.ans2(num);
    ret = s.ans3(num);
    s.show(ret);
}

void test2(){
    vector<int> num = {-1, 1, 0, -3, 3};
    vector<int> ret;

    Solution s;
    // ret = s.ans1(num);
    // ret = s.ans2(num);
    ret = s.ans3(num);
    s.show(ret);
}

int main(void){
    test1();
    test2();

    return 0;
}